#! /usr/bin/python
#! encoding: utf8

__author__ = "kirienko"

from spine import nx_graph_from_str
import networkx as nx
import itertools as it

import graph_state_config_with_fields
import graphine

## Filters
connected = graphine.filters.connected
oneIR = graphine.filters.one_irreducible
@graphine.filters.graph_filter
def self_energy(sub_graph_edges, super_graph):
    """
    Filter for self-energy subgraphs (with 2 external legs)
    """
    if len(sub_graph_edges):
        if len([e for e in sub_graph_edges if e.is_external()])==2:
            return True
    return False

def test(seq,rules):
    for comp in rules:
        if False in map(lambda (x,y):seq.index(x)<seq.index(y),comp):
            return
    return seq


def is_significant_subgraph(sg,tv):
    """
    Returns True if subgraph 'sg' is significant for time version 'tv',
        False otherwise.
    Significance means that all nodes of subgraph appear in the time version
    sequentially, with no breakage (the order of nodes does not matter). 
    E.g. for the time version [0,1,2,3,4,5] the subgraph [3,2,4] is significant,
    whereas [2,4,5] is not. 
    """
    for i,v in enumerate(tv):
        if v in sg:
            if sorted(tv[i:i+len(sg)]) == sg:
                return True
            else:
                return False


def time_vers(nickel_str):
    """
    Returns all time versions of a graph G with Nickel representation 'nickel_str',
        along with all significant subgraphs that correspond every time version:
    >>> time_vers(x)
    ...
     
    Directed edges in our diagram form directed acyclic graph (DAG) with a root 'root'.
    
    """
    U = nx_graph_from_str(nickel_str)
    Z = U.to_undirected()
    T =  nx.DiGraph()
    for e1 in Z.edge:   
        for e2 in U.edge[e1]:
            for k in U[e1][e2]:
                if 'A' in U[e1][e2][k]['fields']:
                    idx = str(U[e1][e2][k]['fields']).index('A')
                    from_node = (e1,e2)[1-idx]
                    to_node   = (e1,e2)[idx] 
                    #print (from_node,to_node,k),U[e1][e2][k],idx
                    T.add_edge(from_node,to_node)
    ## Find all self-energy subgraphs
    G = graph_state_config_with_fields.from_str(nickel_str)
    subgraphs = [x for x in G.x_relevant_sub_graphs(filters=connected+oneIR+self_energy)]
    sg_nodes  = [sorted([v for v in sg.vertices if v>0]) for sg in subgraphs]

    ## Find the root of DAG:
    root   = [i for i in T.node if T.in_degree(i) == 0][0] 
    if root < 0:
        T.remove_node(root)
        root = [i for i in T.node if T.in_degree(i) == 0][0] 
    ## Nodes of DAG:
    nodes = list(set(T.nodes())-set([root]))
    ## Leaves of DAG:
    leaves = [l for l in T.nodes() if T.out_degree(l)==0]   
    ## Find all paths from root to every leaf:
    paths = []
    for i in leaves:
        paths += [i for i in nx.algorithms.all_simple_paths(T,root,i)]
    ## Comparison rules for every two nodes that define whether
    ##      time version is correct: 
    test_cmp = [[i for i in it.combinations(p,2)] for p in paths]
    ## Find all possible permutations of nodes   
    perm = [[root]+list(i) for i in it.permutations(nodes,len(nodes))]
    ## Apply the rules of comparison
    vers = []
    for p in perm:
        ver = test(p,test_cmp)
        if ver:
            ## Test if subgraph is significant for this time version
            vers += [(ver,\
                [subgraphs[i] for i, sg in enumerate(sg_nodes) if
                    is_significant_subgraph(sg,ver)
                 and '0A' in str(subgraphs[i])
                 and '0a' in str(subgraphs[i])])]
    return vers

if  __name__ == "__main__":
    Loops = 3
    #with open('%dloop_nonzero.txt'%Loops) as fd:
    #    diags = [d.strip() for d in fd.readlines()]
 
    vasya = 'e12|e3|34|5|55||:0A_aA_dA|0a_dA|dd_aA|aa|aA_dd||'
    one   = 'e12|e3|34|5|55||:0A_dd_aA|0a_Aa|dd_aA|Aa|aA_dd||' # one time version
    no_one= 'e12|e3|45|45|5||:0A_aA_dA|0a_dA|aA_dd|aa_dA|da||' # no time versions

    vers = time_vers(no_one)

